package homework2.FibonacciNumbers;

import java.math.BigInteger;

import javax.swing.JOptionPane;

/**
 * Fibonacci-Numbers calculate class which contains three calculate method.
 * 
 * @author eDisOn 2009212634 lilh09@mails.tsinghua.edu.cn
 */
public class FibonacciNumbers
{
	/**
	 * Calculate fibonacci number via original recursive method f(n) = f(n-1) +
	 * f(n-2)
	 * 
	 * @param n
	 *            input n
	 * @return the fibonacci number for the input n
	 */
	public int fibonacci(int n)
	{
		if (n < 2)
			return n;
		else
			return fibonacci(n - 1) + fibonacci(n - 2);
	}

	/**
	 * Calculate fibonacci number via BottomUp method that is f(2) = f(1) + f(0)
	 * -> f(3) = f(2) + f(1)...
	 * 
	 * The time complexity is O(n)
	 * 
	 * @param n
	 *            input n
	 * @return the fibonacci number for the input n
	 */
	public BigInteger fibonacciByBottomUp(Integer n)
	{
		if (n < 2)
			return new BigInteger(n.toString());
		else
		{
			BigInteger first = new BigInteger("0");
			BigInteger second = new BigInteger("1");
			BigInteger result = new BigInteger("0");

			int i = 2;
			while (i <= n)
			{
				result = first.add(second);

				first = second;
				second = result;

				i++;
			}
			return result;
		}
	}

	/**
	 * Calculate fibonacci number via matrix multiple method that is: |f(n+1)
	 * f(n)| = |1 1| |f(n) f(n-1)| |1 0|
	 * 
	 * The time complexity is O(ln(n))
	 * 
	 * @param n
	 *            input n
	 * @return the fibonacci number for the input n
	 */
	public BigInteger fibonacciByMatrixMulti(int n)
	{
		Matrix basic = new Matrix(new BigInteger("1"), new BigInteger("1"),
				new BigInteger("1"), new BigInteger("0"));

		return matrixPow(basic, n).b;
	}

	/**
	 * matrix pow function which based on recursive method.
	 * 
	 * @param matrix
	 * @param size
	 * @return
	 */
	private Matrix matrixPow(Matrix matrix, int size)
	{
		if (size == 1)
		{
			return matrix;
		}
		else
		{
			Matrix result = new Matrix(null, null, null, null);

			Matrix subMatrix = matrixPow(matrix, size >> 1);

			result.a = subMatrix.a.pow(2)
					.add(subMatrix.b.multiply(subMatrix.c));
			result.b = subMatrix.a.multiply(subMatrix.b).add(
					subMatrix.b.multiply(subMatrix.d));
			result.c = result.b;
			result.d = subMatrix.b.multiply(subMatrix.c)
					.add(subMatrix.d.pow(2));

			// size is odd
			if ((size & 1) == 1)
			{
				BigInteger tmpA = new BigInteger(result.a.toByteArray());
				BigInteger tmpC = new BigInteger(result.c.toByteArray());
				result.a = result.a.add(result.b);
				result.b = tmpA;
				result.c = result.c.add(result.d);
				result.d = tmpC;
			}
			return result;
		}
	}

	public static void main(String args[])
	{
		int input = 0;
		do
		{
			try
			{
				String strInput = JOptionPane
						.showInputDialog("Please input an integer n:");
				if (strInput == null)
				{
					System.exit(1);
				}
				else
				{
					input = Integer.parseInt(strInput);
				}
			}
			catch (NumberFormatException nfe)
			{
				JOptionPane.showMessageDialog(null, "Plase input an integer");
				continue;
			}

			if (input <= 0)
			{
				JOptionPane.showMessageDialog(null,
						"Plase input a positive number!");
			}
			else
			{
				break;
			}
		}
		while (true);

		FibonacciNumbers calculator = new FibonacciNumbers();
		long time4ori, time4BottomUp, time4MatrixMulti;
		long start = System.nanoTime();
		String output = "*****************Result*****************\n";
		if (input <= 50)
		{
			start = System.nanoTime();
			int firResult = calculator.fibonacci(input);
			time4ori = System.nanoTime() - start;
			output += "Original method output:" + firResult;
			output += "\t\n";
			output += "   -Time : " + time4ori / 1000 + " (μs)\n";
		}

		start = System.nanoTime();
		BigInteger secResult = calculator.fibonacciByBottomUp(input);
		time4BottomUp = System.nanoTime() - start;
		if (secResult.toString().length() > 20)
		{
			output += "BottonUp method output:"
					+ secResult.toString().substring(0, 20) + "...";
		}
		else
		{
			output += "BottonUp method output:" + secResult;
		}
		output += "\t\n";
		output += "   -Time : " + time4BottomUp / 1000 + " (μs)\n";

		start = System.nanoTime();
		BigInteger thiResult = calculator.fibonacciByMatrixMulti(input);
		time4MatrixMulti = System.nanoTime() - start;
		if (thiResult.toString().length() > 20)
		{
			output += "MatrixMulti method output:"
					+ thiResult.toString().substring(0, 20) + "...";
		}
		else
		{
			output += "Matrix Multiple method output:" + thiResult.toString();
		}
		output += "\t\n";
		output += "   -Time : " + time4MatrixMulti / 1000 + " (μs)\n";

		JOptionPane.showMessageDialog(null, output);
	}
}

class Matrix
{
	public BigInteger a, b, c, d;

	public Matrix(BigInteger initA, BigInteger initB, BigInteger initC,
			BigInteger initD)
	{
		a = initA;
		b = initB;
		c = initC;
		d = initD;
	}
}